跳转至

题解：P12315 [蓝桥杯 2024 国 C] 挑苹果

\(\mathbf{upd\ 2025/5/14}\)：文章内容纠错，并统一 Markdown 格式（保证 \(\LaTeX\) 被正确使用）

思路与算法

本题目解题的核心思想是通过数学推导和事件统计，计算出满足条件 \(l > r\) 的最大苹果数量。

我们这里称事件为一个特定的点和它的变化量，用来表示在某个位置上美味值的变化。这些事件的作用是通过扫描线算法来计算每个位置上满足条件的苹果数量。

通过对这些事件按位置排序，然后依次处理，可以高效地计算出满足条件的苹果的最大数量。

事件统计部分

区间计算

由题，我们需要使得每种苹果的美味值 \(a_i\) 经过操作后满足条件：\(\((a_i + x) \bmod k \le t\)\)

接着，让我们推导 \(x\) 的范围。易知，\((x + m) \bmod k \le t\) 等价于：\(x \bmod k \in [(k - m) \bmod k, (k - m + t) \bmod k]\)

则我们令：

  • \(l\) 是模运算的下界，且有 \(l = (k - m) \bmod k\)；
  • \(r\) 是模运算的上界，且有 \(r = (l + t) \bmod k\)。

则我们得到了满足条件的 \(x\) 的取值范围 \([l, r]\)，方便进行后续统计。

特别地：如果区间跨越了模数边界（\(l > r\)），需要分段处理。

事件统计

为了高效统计满足条件的 \(x\) 的数量，这里我们使用差分数组的思想，将区间 \([l , r]\) 转化为事件。

在区间 \([l, r]\) 的起点 \(l\) 增加 \(1\)，表示区间开始。在区间的终点 \(r + 1\) 减少 \(1\)，表示区间结束。如果区间跨越边界，则分段处理两部分。

具体地，当遍历每个苹果的美味值 \(a_i\) 时，计算其余数 \(m = a_i \bmod k\)，此时： - 根据 \(t\) 和 \(k\)，计算满足条件的区间 \([l, r]\)： - 如果 \(l \le r\)，发生两个事件： - 在 \(l\) 位置增加 1; - 在 \(r+1\) 位置减少 1。 - 如果 \(l \gt r\)（即区间跨越边界时），发生四个事件： - 在 \(l\) 位置增加 1; - 在 \(k\) 位置减少 1; - 在 \(0\) 位置增加 1; - 在 \(r + 1\) 位置减少 1。

它的作用是通过统计事件，将区间操作转化为点操作，便于后续排序和扫描统计。

该部分代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
vector<pair<int, int>> events;
for (int i = 0; i < n; ++i) {
    int m = a[i] % k;
    int l, r;
    if (t >= k) {
        l = 0;
        r = k - 1;
    } else {
        l = (k - m) % k;
        r = (l + t) % k;
        if (l <= r) {
            events.emplace_back(l, 1);
            events.emplace_back(r + 1, -1);
        } else {
            events.emplace_back(l, 1);
            events.emplace_back(k, -1);
            events.emplace_back(0, 1);
            events.emplace_back(r + 1, -1);
        }
    }
}

p.s:

在这里事件被存储在 events 数组中，每个事件是一个 pair<int, int>，其中：

  • first 表示位置pos，即模 k 的余数范围的起点或终点。
  • second 表示变化量delta，可以是 1（即表示开始增加）或 -1（即表示开始减少）。

具体来说：

  • 当 delta 为 1 时，表示从这个位置开始，满足条件的苹果数量增加。
  • 当 delta 为 -1 时，表示从这个位置开始，满足条件的苹果数量减少。

事件排序与扫描部分

接下来，根据我们最开始提到的，我们要对数组进行排序。

事件排序

按照位置 pos 对事件排序，确保扫描时按顺序处理，这里直接使用 sort() 函数即可。

扫描统计

遍历事件，维护当前活跃区间的计数 current，并在每次位置变化时，更新最大值 max_count。

本部分代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
sort(events.begin(), events.end());
int max_count = 0;
int current = 0;
int prev_pos = 0;
for (const auto& event : events) {
    int pos = event.first;
    int delta = event.second;
    if (pos > prev_pos) {
        max_count = max(max_count, current);
    }
    current += delta;
    prev_pos = pos;
}
max_count = max(max_count, current);

代码

最后献上我的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
const int MAX_EVENTS = 200005; // 记得开2倍
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k, t;
    cin >> n >> k >> t;
    int a[100005]; 
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int diff[100005] = {0};
    pair<int, int> events[MAX_EVENTS]; 
    int event_count = 0;
    for (int i = 0; i < n; ++i) {
        int m = a[i] % k;
        int l, r;
        if (t >= k) {
            l = 0;
            r = k - 1;
        } else {
            l = (k - m) % k;
            r = (l + t) % k;
            if (l <= r) {
                events[event_count++] = {l, 1};
                events[event_count++] = {r + 1, -1};
            } else {
                events[event_count++] = {l, 1};
                events[event_count++] = {k, -1};
                events[event_count++] = {0, 1};
                events[event_count++] = {r + 1, -1};
            }
        }
    }
    if (t >= k) {
        cout << n << endl;
        return 0;
    }
    sort(events, events + event_count);
    int max_count = 0;
    int current = 0;
    int prev_pos = 0;
    for (int i = 0; i < event_count; ++i) {
        int pos = events[i].first;
        int delta = events[i].second;
        if (pos > prev_pos) {
            max_count = max(max_count, current);
        }
        current += delta;
        prev_pos = pos;
    }
    max_count = max(max_count, current);
    cout << max_count << endl;
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
using System;
using System.Collections.Generic;

class Program
{
    const int MAX_EVENTS = 100005;

    static void Main()
    {
        int n, k, t;
        string[] input = Console.ReadLine().Split();
        n = int.Parse(input[0]);
        k = int.Parse(input[1]);
        t = int.Parse(input[2]);

        int[] a = new int[n];
        input = Console.ReadLine().Split();
        for (int i = 0; i < n; ++i)
        {
            a[i] = int.Parse(input[i]);
        }

        List<(int, int)> events = new List<(int, int)>();
        for (int i = 0; i < n; ++i)
        {
            int m = a[i] % k;
            int l, r;
            if (t >= k)
            {
                l = 0;
                r = k - 1;
            }
            else
            {
                l = (k - m) % k;
                r = (l + t) % k;
                if (l <= r)
                {
                    events.Add((l, 1));
                    events.Add((r + 1, -1));
                }
                else
                {
                    events.Add((l, 1));
                    events.Add((k, -1));
                    events.Add((0, 1));
                    events.Add((r + 1, -1));
                }
            }
        }

        if (t >= k)
        {
            Console.WriteLine(n);
            return;
        }

        events.Sort((x, y) => x.Item1.CompareTo(y.Item1));

        int maxCount = 0;
        int current = 0;
        int prevPos = 0;

        foreach (var eventPair in events)
        {
            int pos = eventPair.Item1;
            int delta = eventPair.Item2;

            if (pos > prevPos)
            {
                maxCount = Math.Max(maxCount, current);
            }

            current += delta;
            prevPos = pos;
        }

        maxCount = Math.Max(maxCount, current);
        Console.WriteLine(maxCount);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int t = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        if (t >= k) {
            System.out.println(n);
            return;
        }

        List<Event> events = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int m = a[i] % k;
            int l, r;
            if (t >= k) {
                l = 0;
                r = k - 1;
            } else {
                l = (k - m) % k;
                r = (l + t) % k;
                if (l <= r) {
                    events.add(new Event(l, 1));
                    events.add(new Event(r + 1, -1));
                } else {
                    events.add(new Event(l, 1));
                    events.add(new Event(k, -1));
                    events.add(new Event(0, 1));
                    events.add(new Event(r + 1, -1));
                }
            }
        }

        events.sort(Comparator.comparingInt(e -> e.pos));

        int maxCount = 0;
        int current = 0;
        int prevPos = 0;
        for (Event event : events) {
            int pos = event.pos;
            int delta = event.delta;
            if (pos > prevPos) {
                maxCount = Math.max(maxCount, current);
            }
            current += delta;
            prevPos = pos;
        }
        maxCount = Math.max(maxCount, current);

        System.out.println(maxCount);
    }

    static class Event {
        int pos;
        int delta;

        Event(int pos, int delta) {
            this.pos = pos;
            this.delta = delta;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Event:
    def __init__(self, pos, delta):
        self.pos = pos
        self.delta = delta

def main():
    n, k, t = map(int, input().split())
    a = list(map(int, input().split()))

    if t >= k:
        print(n)
        return

    events = []
    for i in range(n):
        m = a[i] % k
        if t >= k:
            l, r = 0, k - 1
        else:
            l = (k - m) % k
            r = (l + t) % k
            if l <= r:
                events.append(Event(l, 1))
                events.append(Event(r + 1, -1))
            else:
                events.append(Event(l, 1))
                events.append(Event(k, -1))
                events.append(Event(0, 1))
                events.append(Event(r + 1, -1))

    events.sort(key=lambda e: e.pos)

    max_count = 0
    current = 0
    prev_pos = 0
    for event in events:
        pos = event.pos
        delta = event.delta
        if pos > prev_pos:
            max_count = max(max_count, current)
        current += delta
        prev_pos = pos
    max_count = max(max_count, current)

    print(max_count)

if __name__ == "__main__":
    main()